Paper 2015/163

Indistinguishability Obfuscation from Functional Encryption

Nir Bitansky and Vinod Vaikuntanathan

Abstract

Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. Prior candidate IO constructions were based on specific assumptions on algebraic objects called multi-linear graded encodings. We present a generic construction of indistinguishability obfuscation from public-key functional encryption with succinct encryption circuits and subexponential security. This shows the equivalence of indistinguishability obfuscation and public-key functional en- cryption, a primitive that has previously seemed to be much weaker, lacking the power and the staggering range of applications of indistinguishability obfuscation. Our main construction can be based on functional encryption schemes that support a single functional key, and where the encryption circuit grows sub-linearly in the circuit-size of the function. We further show that sublinear succinctness in circuit-size for single-key schemes can be traded with sublinear succinctness in the number of keys (also known as the collusion-size) for multi-key schemes. We also show that, under the Learning with Errors assumption, our techniques imply that any indistinguishability obfuscator can be converted into one where the size of obfuscated circuits is twice that of the original circuit plus an additive overhead that is polynomial in its depth, input length, and the security parameter.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. FOCS 2015
Keywords
obfuscationfunctional encryption
Contact author(s)
nbitansky @ gmail com
History
2018-07-03: last of 5 revisions
2015-02-27: received
See all versions
Short URL
https://ia.cr/2015/163
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/163,
      author = {Nir Bitansky and Vinod Vaikuntanathan},
      title = {Indistinguishability Obfuscation from Functional Encryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/163},
      year = {2015},
      url = {https://eprint.iacr.org/2015/163}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.